\chapter{k-перестановки из n-элементов}

Честно говоря забыл какого числа была лекция, но в общем на ней было про двойственные задачи, контрольная была еще... первая...

\subsection{k-перестановки из n-элементов}

Не тру называть раздел и подраздел одинакоо, но да не обращайте внимания.

\begin{Def}
Пусть $X=\{x_1, ... ,x_n\}$ - конечное множество элементов. Упорядоченный набор $\left(a_1, ... ,a_k\right)$ назыввается:
\begin{itemize}
	\item k-перестановка из n элементов

	\item k-размещение из n элементов

	\item кортеж из n элементо длины k

	\item k-элементное слово над алфавитом X

	\item k-вектор из n
\end{itemize}
В случае, если допустимы повторения, т.е. $a_i=a_j$ при $i \ne j$ говорят о
k-перестаноке с повторениями.
\end{Def}

\begin{Th}[О количестве k-перестаноок из n с повторениями]
$\left|X^{\left(k\right)}\right| = {\left|X\right|}^k$

$\left|X^{\left(k\right)}\right|$ - все слова длинны k над алфовитом $X$ 
\label{math::k_perm}
\end{Th}

Воспользуемся теоремкой \ref{math::k_perm} для комбинаторного доказательства известного соотношения:
\[
	2^n = \sum _{k=0} ^n \binom{n}{k}
\]

Закодируем каждое подмножесто $Y \subseteq X^k$ двоичным n-вектором, где $\left|X\right| = n$. Кодирование проивзодим следующим образом:
\[
	\underbrace{
		\left(\varepsilon_1, \varepsilon_2, ... \varepsilon_n\right)
	}_n
\]
в формуле $\varepsilon_i = 1$, если $x_i \in Y$ и $\varepsilon_i = 0$ иначе.

Получили множесто двоичных n-векторов, количество таких векторов $2^n$

\begin{Def}
${\left(n\right)}_k = P\left(n,k\right)$ - обрезанный факториал, считается следующим образом ${\left(n\right)}_k = \prod_{i=0}^{k-1} \left(n-i\right)$
\end{Def}

\paragraph{Следствие 1.} при $k=n$, получаем перестановку из $n$ элементов
\[
	P\left(k=n,n\right) = P\left(n\right) = n!
\]

\paragraph{Следствие 2.} $P\left(n\right) = P \left(n, n\right) = P\left(n,n-1\right)$

\paragraph{Следствие 3.}
\[
	\binom{n}{k} k! = {\left(n\right)}_k \Rightarrow \binom{n}{k} = \frac{{\left(n\right)}_k}{k!} = \frac{n!}{k!\left(n-k\right)}
\]

\begin{Th}
\[
	\begin{split}
		& P\left(n,k\right) = P\left(n-1,k\right)+k P\left(n-1,k-1\right)\\
		& P\left(n,0\right) = 1, \forall n \ge 0 \\
		& P\left(n,k\right) = 0, \forall k > n
	\end{split}
\]
\end{Th}

\begin{Proof}
Комбинаторное доказательство. Как и в двух прошлых случаях, выделим один элемент из множества $X$ и разобьем все k-перестановки из n элементов, относительно выбранного элемента на два множества, первое ($\sum_{x \notin}$) содержит перстановки не содержащие выделенный элемент, а второе ($\sum_{x \in}$) содержит перестановки с этим элементом, причем выбранный элемент может стоять на любой из $k$ позиций. Мощности этих множеств:
\begin{itemize}
	\item $\left|\sum_{x \not\in}\right| = P\left(n-1,k\right)$

	\item $\left|\sum_{x \in}\right| = k \cdot P\left(n-1, k-1\right)$
\end{itemize}
\end{Proof}

\begin{Proof}
Доказательство, простите, аналитическое.
\begin{multline*}
	\prod_{i=0}^{k-1}\left(n-i\right) = n \cdot \prod_{i=1}^{k-1} \left(n-i\right) = \\
	= n \cdot \prod_{i=0}^{k-2} \left(n-1-i\right) = \left(n-k+k\right) \cdot \prod_{i=0}^{k-2} = \\ 
	= \left(n-k\right) \cdot \prod_{i=0}^{k-2} \left(n-1-i\right)+k \cdot \prod_{i=0}^{k-2} \left(n-1-i\right) = \\ 
	= P\left(n-1,k\right) + k \cdot P \left(n-1, k-1\right)
\end{multline*}
\end{Proof}

\section{Домашние задания - задачи}

Ну тут в общем совсем немного, мы рассмотрим решение двух схожих задач, а именно решение целочисленных уравнений с ограничениями.

\paragraph{Задача 1.} Пусть имеется уравнение $\sum_{i=1}^{n} a_i = k$. Необходимо узнать сколько целочисленных решений имеет это уравнение, при следующих ограничениях:
\begin{itemize}
\item $a_i \ge S_i$

\item $S = \sum_{i=1}^{n} S_i \le k$
\end{itemize}

т. е. на каждую переменную наложено ограничение снизу, в этом случае все очень просто, ход мыслей такой, мы делим $k$ единиц между $n$ позициями (переменными) с повторениями, а ограничение говорит только о том, что $S$ единиц уже распределены, таким образом осталось распределить $k-S$ единиц:
\[
	\left( \binom{n}{k-S} \right)
\]

\paragraph{Задача 2.} Пусть имеется уравнение $\sum_{i=1}^{n} a_i = k$. Необходимо опять же найти все его целочисленные решения, но уже со следующими ограничениями:
\begin{itemize}
\item $a_i \le m_i$

\item $m = \sum _{i=1}^{n} \ge k$
\end{itemize}
На вид все кажется просто, когда начинаешь думать, все оказывается сложно, а потом все опять становится просто, но уже очень поздно.

Пойдем путем наблюдений. Пусть $m=k$, то количество решений очевидно равно одному, далее рассмотрим случай $m=k+1$, в данном случае на всех переменных кроме одной будет выполняться условие $a_i = m_i$, а на одной $a_j + 1 = m_j$, т. е. мы выбираем среди n позиций одну. Далее рассмотрим $m=k+2$, по аналогии, выбираем среди n позиций 2, с повторениями и тд. Таким образом мы распределяем $m-k$ единиц "недобора" до границ $m_i$ с повторениями между $n$ границами:
\[
	\left(\binom{n}{m-k}\right)
\] 
